class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val 
        self.left=left 
        self.right=right

from collections import deque
def build_level(lst):
    root=TreeNode(lst[0])
    que=deque([root])
    i=1 
    while len(que)>0 and i<len(lst):
        cur=que.popleft()
        if lst[i]: 
            cur.left=TreeNode(lst[i])
            que.append(cur.left)
        if i+1<len(lst) and lst[i+1]:
            cur.right=TreeNode(lst[i+1])
            que.append(cur.right)
        i+=2 
    return root 

def solve(root,k):
    n=0 
    ans=None
    def traversal(root,k):
        nonlocal ans 
        nonlocal n 
        if root.left: traversal(root.left,k) #1）
        if n==k: return #2）
        ans=root.val 
        n+=1 
        if root.right: traversal(root.right,k)
    traversal(root,k)
    return ans


# def solve(root,k):
#     n=0
#     val=None
#     def traversal(root,k):
#         nonlocal n
#         nonlocal val
#         if root.left: traversal(root.left,k)
#         if n==k: return
#         val=root.val
#         n+=1
#         if root.right: traversal(root.right,k)
#     traversal(root,k)
#     return val







# def solve(root,k):   
#     def traversal(root,lst,k):
#         if root.left: traversal(root.left,lst,k)
#         if len(lst)==k: return
#         lst.append(root.val)
#         if root.right: traversal(root.right,lst,k)
#     lst=[]
#     traversal(root,lst,k)
#     return lst[-1]



# def solve(root,k):   
#     def traversal(root,k):
#         nonlocal ans
#         if root.left: traversal(root.left,k)
#         if k==0: 
#             print('*',ans)
#             return
#         if root: 
#             print('**',k)
#             ans=root.val 
#             #lst.append(root.val)
#             k-=1
#         if root.right: 
#             print('***',k)
#             traversal(root.right,k)
#     ans=None
#     #lst=[]
#     traversal(root,k)
#     return ans




root=build_level([3,1,4,None,2])
print(solve(root,1))
root=build_level([5,3,6,2,4,None,None,1])
print(solve(root,3))



